#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>


//void Swap(int* p1, int* p2) {
//
//	int tmp = *p1;
//	*p1 = *p2;
//	*p2 = tmp;
//
//}

//void AdjustUp(int* a, int child) {
//	int parent = (child - 1) / 2;
//	while (child > 0) {
//		if (a[parent] < a[child]) {
//
//			Swap(&a[parent],&a[child]);
//			child = parent;
//			parent = (child - 1) / 2;
//
//		}
//		else { break; }
//	}
//}
//
//void AdjustDown(int* a, int n, int parent) {
//	int child = parent * 2 + 1;
//	while (child < n) {
//		if (child+1<n&&a[child] < a[child + 1]) {
//			++child;
//		}
//		if (a[child] > a[parent]) {
//			Swap(&a[parent],&a[child]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else { break; }
//	}
//}
//
//
//void main() {
//
//	int a[] = { 12,2,333,45,9,200,122,210,56,666 };
//	int n = sizeof(a) / sizeof(a[0]);
//	for (int i = 1; i < n; i++) {
//		AdjustUp(a, i);
//	}
//	int k = 8;
//	int end = n - 1;
//	while (k--) {
//		Swap(&a[0], &a[end]);
//		printf("%d ", a[end]);
//		AdjustDown(a, end, 0);
//		--end;
//	}
//
//
//
//
//	return 0;
//}

typedef struct BTNode {
	
	int val;
	struct BTNode* left;
	struct BTNode* right;

}BTNode;


BTNode* BTBuyNode(int x) {

	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL) {
		printf("malloc failed");
		exit;
	}
	newnode->val = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;


}

BTNode* BTInit() {

	BTNode* node1 = BTBuyNode(1);
	BTNode* node2 = BTBuyNode(2);
	BTNode* node3 = BTBuyNode(3);
	BTNode* node4 = BTBuyNode(4);
	BTNode* node5 = BTBuyNode(5);
	BTNode* node6 = BTBuyNode(6);
	BTNode* node7 = BTBuyNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node2->right = node5;
	//node3->left = node6;
	node4->left = node6;
	//node3->right = node7;
	//node4->right = node6;

	return node1;

}

//BTNode* FrontOrder(BTNode*root) {
//
//	if (root == NULL)
//	{
//		printf("N->");
//		return;
//	}
//
//	printf("%d->", root->val);
//	FrontOrder(root->left);
//	FrontOrder(root->right);
//
//
//}
//
//BTNode* InOrder(BTNode* root) {
//
//	if (root == NULL)
//	{
//		printf("N->");
//		return;
//	}
//
//	InOrder(root->left);
//	printf("%d->", root->val);
//	InOrder(root->right);
//
//}
//
//BTNode* BackOrder(BTNode* root) {
//
//	if (root == NULL)
//	{
//		printf("N->");
//		return;
//	}
//
//	BackOrder(root->left);
//	BackOrder(root->right);
//	printf("%d->", root->val);
//
//}
//

int NodeNumber(BTNode* root) {


	if(root==NULL)
	{
		return 0;
	}

	return 1+NodeNumber(root->left) + NodeNumber(root->right);


}


int LeafNumber(BTNode*root){

	if (root == NULL)
		return 0;
	
	if (root->left== NULL && root->right == NULL) {
		return 1;
	}

 
	return LeafNumber(root->left) + LeafNumber(root->right);

}


int TreeHeight(BTNode* root) {

	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL) {
		return 1;
	}
	/*BTNode*leftNode = root->left;
	BTNode*rightNode = root->right;*/


	return 1+max(TreeHeight(root->left),TreeHeight(root->right));



}

int KNodeNumber(BTNode* root, int k) {

	if (root == NULL)
		return 0;

	if (k == 1) {
		return 1;
	}

	return KNodeNumber(root->left, k - 1) + KNodeNumber(root->right, k - 1);


}

#include"Queue.h"
void LevelNode(BTNode* root) {

	Queue q;
	QueueInit(&q);
    if(root)
	{
		QueuePush(&q, root);
	}
	while(!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->val);
		if (front->left) {
			QueuePush(&q, front->left);
		}
		if (front->right) {
			QueuePush(&q, front->right);
		}
	}

	QueueDestroy(&q);
}

bool TreeComplete(BTNode* root) {

	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL) {
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
		
	}
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front) {
			QueueDestroy(&q);
			return false;
		}
	

	}
	QueueDestroy(&q);
	return true;
}

void TreeDestroy(BTNode* root) {
	if (root==NULL)
		return;
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

int main() {

	BTNode* root = BTInit();

	/*FrontOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	BackOrder(root);*/

	printf("NodeNumber:%d\n", NodeNumber(root));
	printf("LeafNumber:%d\n", LeafNumber(root));
	printf("TreeHeight:%d\n", TreeHeight(root));
	printf("KNodeNumber:%d\n", KNodeNumber(root,4));
	LevelNode(root);
	printf("\n");
	printf("%d",TreeComplete(root));

	TreeDestroy(root);
	return 0;
}




